import random


class Sort:
    def __init__(self, arr_len):
        # self.arr = []
        self.arr = [3, 87, 2, 93, 78, 56, 61, 38, 12, 40]
        self.arr_len = arr_len
        self.temp_arr = [0] * self.arr_len

    def random_list(self):
        for i in range(self.arr_len):
            self.arr.append(random.randint(0, 99))

    def bubble(self):
        arr = self.arr
        i = self.arr_len - 1
        while i > 0:
            j = 0
            flag = 1
            while j < i:
                if arr[j] > arr[j + 1]:  # 把最小的换到开头
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 冒泡比小一次换一次
                flag = 0
                j += 1
            if flag:
                break
            i -= 1

    def select(self):
        arr = self.arr
        for i in range(self.arr_len - 1):
            min_pos = i
            for j in range(i + 1, self.arr_len):
                if arr[j] < arr[min_pos]:  # 从小到大排序
                    min_pos = j
            arr[i], arr[min_pos] = arr[min_pos], arr[i]  # 比冒泡少交换，这个比一轮只换一次

    def insert(self):
        arr = self.arr
        i = 1
        while i < self.arr_len:
            insertVar = arr[i]
            j = i - 1
            while j >= 0 and arr[j] > insertVar:
                arr[j + 1] = arr[j]
                j -= 1
            arr[j + 1] = insertVar
            i += 1

    # 王道书方法快排
    def partition(self, left, right):
        arr = self.arr
        pivot = left
        while left < right:
            if arr[pivot] < arr[right]:
                right -= 1
            else:
                arr[pivot], arr[right] = arr[right], arr[pivot]
            if arr[pivot] > arr[left]:
                left += 1
            else:
                arr[pivot], arr[left] = arr[left], arr[pivot]
        return pivot

    def quick(self, left, right):#递归我觉得快排是顺着手算方法写的，归并是逆着手算方法写的
        if left < right:
            pivot = self.partition(left, right) #划分
            self.quick(left, pivot - 1)#对左边快排
            self.quick(pivot + 1, right)#对右边快排

    # 调整大根堆
    def adjust_max_heap(self, dad, arr_len):
        arr = self.arr
        son = 2 * dad + 1
        while son < arr_len:
            if son + 1 < arr_len and arr[son] < arr[son + 1]:
                son += 1
            if arr[son] > arr[dad]:
                arr[son], arr[dad] = arr[dad], arr[son]
                dad = son
                son = 2 * dad + 1
            else:
                break

    # 堆排序
    def heap_sort(self):
        arr = self.arr
        for i in range(self.arr_len // 2 - 1, -1, -1):  # 也就是从最后一个非叶结点，往根那边一个个调整，所以 下标是倒着的所以步长是-1
            self.adjust_max_heap(i, self.arr_len)
        arr[0], arr[self.arr_len - 1] = arr[self.arr_len - 1], arr[0]
        # 这里是在不断控制 待排的无序数组的长度 ，是不断地把最后的叶子结点排除
        for i in range(self.arr_len - 1, 1, -1):
            self.adjust_max_heap(0, i)
            arr[0], arr[i - 1] = arr[i - 1], arr[0]

    # 归并
    def merge(self, low, mid, high):
        temp_arr = self.temp_arr
        arr = self.arr
        temp_arr[low:high + 1] = arr[low:high + 1]  # 左闭右开，也就是把原数组复制一份到临时数组里
        i=low
        j=mid+1
        k=low
        while i<=mid and j<=high:
            #比较两组，把小的拿出来放在归并完的数组里
            if temp_arr[i]<temp_arr[j]:
                arr[k]=temp_arr[i]
                i+=1
                k+=1
            else:
                arr[k]=temp_arr[j]
                j+=1
                k+=1
        #如果某一边剩多了，直接复制过来到归并后的数组里
        while i<=mid:
            arr[k]=temp_arr[i]
            i+=1
            k+=1
        while j<=high:
            arr[k]=temp_arr[j]
            j+=1
            k+=1

    def b_merge_sort(self,low,high):#递归我觉得快排是顺着手算方法写的，归并是逆着手算方法写的
        if low<high:
            mid=(low+high)//2
            self.b_merge_sort(low,mid)
            self.b_merge_sort(mid+1,high)
            self.merge(low,mid,high)


if __name__ == '__main__':
    # 建列表
    temp = Sort(10)
    # temp.random_list()

    print(temp.arr)

    # 冒泡排序测验
    # temp.bubble()
    # print(temp.arr)

    # 选择排序测验
    # temp.select()
    # print(temp.arr)

    # 插入排序测试
    # temp.insert()
    # print(temp.arr)

    # 快速排序测试
    temp.quick(0, temp.arr_len - 1)
    print(temp.arr)

    # 堆排序测试
    # temp.heap_sort()
    # print(temp.arr)

    #归并排序测试
    # temp.b_merge_sort(0,temp.arr_len-1)
    # print(temp.arr)
